package com.yoshino.leetcode.interview150.binaryTree.binarySearch;

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length - 1, mid;
        while (left <= right) {
            mid = left + (right - left) / 2;
            if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] < target){
                left = mid + 1;
            } else {
                return mid;
            }
        }
        return left;
    }

    public boolean searchMatrix(int[][] matrix, int target) {
        // 根据性质，从右上到左下
        int row = 0, col = matrix[0].length - 1;
        while (row < matrix.length && col >= 0) {
            if (matrix[row][col] < target) {
                row++;
            } else if (matrix[row][col] > target) {
                col--;
            } else {
                return true;
            }
        }
        return false;
    }

    public int findPeakElement(int[] nums) {
        int left = 0, right = nums.length - 1, mid;
        while (left < right) {
            mid = left + (right - left) / 2;
            if (nums[mid] > nums[mid + 1]) {
                right = mid;
            } else {
                // 对于 mid + 2 要么大于 mid + 1 为 mid，小于 取右边
                left = mid + 1;
            }
        }
        return left;
    }

    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1, mid;
        while (left <= right) {
            mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < nums[right]) {
                // 右边有序
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    // 在左边
                    right = mid - 1;
                }
            } else {
                // 右边无序,左边有序
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
        }
        return -1;
    }

    public int[] searchRange(int[] nums, int target) {
        // 先找到，然后左右查找
        if (nums.length == 0 || nums[nums.length - 1] < target || target < nums[0]) {
            return new int[]{-1, -1};
        }
        int left = 0, right = nums.length - 1, mid;
        while (left <= right) {
            mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return new int[] {lsearch(nums, target, left, mid), rsearch(nums, target, mid, right)};
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return new int[] {-1, -1};
    }

    private int rsearch(int[] nums, int target, int left, int right) {
        int mid, index = -1;
        while (left <= right) {
            mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                // 相等
                index = mid;
                // 右边是否还有
                left = mid + 1;
            }
        }
        return index;
    }

    private int lsearch(int[] nums, int target, int left, int right) {
        int mid, index = -1;
        while (left <= right) {
            mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                // 相等
                index = mid;
                // 左边是否还有
                right = mid - 1;
            }
        }
        return index;
    }

    public int findMin(int[] nums) {
        int length = nums.length, left = 0, right = length - 1, mid;
        while (left <= right) {
            mid = left + (right - left) / 2;
            // 有序
            if (nums[left] <= nums[right]) {
                return nums[left];
            } else {
                if (nums[mid] > nums[right]) {
                    // 后面无序
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
        }
        return nums[left];
    }

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        // 避免奇偶总数影响
        int left = (m + n + 1) / 2, right = (m + n + 2) / 2;
        return (findKth(nums1, 0, nums2, 0, left) + findKth(nums1, 0, nums2, 0, right)) / 2.0;
    }

    /**
     * 找最小的第 k 个数
     */
    private int findKth(int[] nums1, int i, int[] nums2, int j, int k) {
       if (i >= nums1.length) {
           // 超过 nums1 长度，为空数组
           return nums2[j + k - 1];
       }
       if (j >= nums2.length) {
           return nums1[i + k - 1];
       }
       if (k == 1) {
           return Math.min(nums1[i], nums2[j]);
       }
       // 每个数组中第 k / 2 位数
       int midVal1 = (i + k / 2 - 1 < nums1.length) ? nums1[i + k / 2 - 1] : Integer.MAX_VALUE;
       int midVal2 = (j + k / 2 - 1 < nums2.length) ? nums2[j + k / 2 - 1] : Integer.MAX_VALUE;
       if (midVal1 < midVal2) {
           // 排除 nums1 中的 k / 2 个
           return findKth(nums1, i + k / 2, nums2, j, k - k / 2);
       } else {
           return findKth(nums1, i, nums2, j + k / 2, k - k / 2);
       }
    }
}